#include <iostream>
#include "SortTestHelper.h"
#include "SelectionSort.h"

using namespace std;

/**
 * 插入排序
 *
 * @param arr
 * @param n
 */
template<typename T>
void insertionSort(T arr[], int n) {
    for (int i = 1; i < n; ++i) {

        //每次内层循环找到应该arr[j]的位置
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {

            swap(arr[j], arr[j - 1]);
        }
    }
}

/**
 * 插入排序,改进版，利用一个单位空间，将一次交换替换为一次赋值
 *
 * @param arr
 * @param n
 */
template<typename T>
void insertionSortBeat(T arr[], int n) {
    for (int i = 1; i < n; i++) {

        //寻找arr[i]的插入位置
        T nux = arr[i];
        int j;      //保存arr[i]应该的插入位置
        for (j = i; j > 0 && arr[j - 1] > nux; j--) {

            arr[j] = arr[j - 1];
        }
        //将nux 放入其应该存在的位置
        arr[j] = nux;
    }
}

int main() {

    //待测数据量
    int n = 10000;

    int *arr = SortTestHelper::generateNearOrderedArray(n, 10);

    int *arr1 = SortTestHelper::copyIntArray(arr, n);

    int *arr2 = SortTestHelper::copyIntArray(arr, n);

    SortTestHelper::testSort("selection sort", selectionSort, arr, n);

    SortTestHelper::testSort("insertion sort", insertionSort, arr1, n);

    SortTestHelper::testSort("insertion sort beat", insertionSortBeat, arr2, n);

    //清除new开辟的内存空间，防止内存泄漏
    delete[] arr;
    delete[] arr1;
    delete[] arr2;
    return 0;
}
